/**
 * 用栈实现
 * @param {*} arr 
 * @param {*} startIndex 
 * @param {*} endIndex 
 */
function quickSort(arr, startIndex, endIndex) {
    //用一个栈来代替递归的的函数栈
    let querySortStack = [];
    //整个数列的起止下标 入栈
    let rootParam={
      startIndex,
      endIndex
    }
    querySortStack.push(rootParam)

    //循环结束条件，栈为空时
    while (querySortStack.length > 0) {
        //栈顶元素出栈，得到起止坐标
        let param = querySortStack.pop();
        // 得到基准元素位置
        let pivotIndex = partition(arr, param.startIndex, param.endIndex);
        // 根据基准元素位置，将数组分为两部分，每一部分入栈
        if (param.endIndex - param.startIndex > 0) {
          let leftParam = {
            startIndex: param.startIndex,
            endIndex: pivotIndex - 1
          }
          querySortStack.push(leftParam);
          let rightParam = {
            startIndex: pivotIndex + 1,
            endIndex: param.endIndex
          }
          querySortStack.push(rightParam);
      }
    }
}
  /**
   * 分支 单边循环法
   * @param {*} arr 
   * @param {*} startIndex 
   * @param {*} endIndex 
   * @returns 
   */
  function partition(arr, startIndex, endIndex) {
    //取第1个位置的元素作为基准元素
    let pivot = arr[startIndex];
    // mark记录比基准元素小的元素的位置
    let mark = startIndex;
    for (let i = startIndex + 1; i <= endIndex; i++) {
      if (arr[i] < pivot) {
        mark++;
        let p = arr[mark];
        arr[mark] = arr[i];
        arr[i] = p;
      }
    }
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
  }
  let arr = [4, 4, 6, 5, 3, 2, 8, 1];
  quickSort(arr, 0, arr.length - 1);
  console.log(arr);